#include <cstdio>

constexpr int M = 2e7 + 5, P = 101, mod = 20170408;
int n, m, p, cnt, f[P], g[P], pri[M], basef[P], baseg[P];
bool vis[M];

inline void mul(int *a, int *b) {
  static int tmp[P];
  for (int i = 0; i < p; ++i) {
    for (int j = 0; j < p; ++j) {
      tmp[i + j] = (tmp[i + j] + 1ll * a[i] * b[j] % mod) % mod;
    }
  }
  for (int i = 0; i < p; ++i) a[i] = (tmp[i] + tmp[i + p]) % mod, tmp[i] = tmp[i + p] = 0;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P3702 [SDOI2017]序列计数.in", "r", stdin);
  freopen("P3702 [SDOI2017]序列计数.out", "w", stdout);
#endif
#endif

  scanf("%d%d%d", &n, &m, &p);
  basef[1] = baseg[1] = f[0] = g[0] = 1;
  for (int i = 2; i <= m; ++i) {
    basef[i % p]++;
    if (!vis[i]) {
      pri[++cnt] = i;
    } else
      baseg[i % p]++;
    for (int j = 1; j <= cnt && pri[j] * i <= m; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
  while (n) {
    if (n & 1) mul(f, basef), mul(g, baseg);
    mul(basef, basef), mul(baseg, baseg);
    n >>= 1;
  }
  printf("%d", ((f[0] - g[0]) % mod + mod) % mod);
  return 0;
}